// 翻译 2163 可以分解成：翻译 2 和剩下的 163 、翻译 21 和剩下的 63

// 每次都有 2 种选择：翻译 1 个数、翻译 2 个数，但有的两位数没有对应的字母，只能翻译 1 个数，只有 1 种选择。
// 指针从左往右扫描，可以画出下面的递归树，2 种选择对应了 2 个分支，1 种选择对应 1 个分支。
// 当指针到达边界或越界，都返回 1 ，使得标记 △△ 的分支返回 0 ，是一条死支。
const translateNum = (num) => {
  const str = num.toString();

  const dfs = (str, pointer) => {
    // 随着dfs向下，pointer右移
    if (pointer >= str.length - 1) return 1; // 指针抵达边界和超出边界都返回1

    const temp = Number(str[pointer] + str[pointer + 1]); // 考察该2位数

    if (temp >= 10 && temp <= 25) {
      return dfs(str, pointer + 1) + dfs(str, pointer + 2); // 2个分支的结果相加
    } else {
      return dfs(str, pointer + 1); // 返回1个分支的结果
    }
  };

  return dfs(str, 0);
};

const translateNum = (num) => {
  const str = num.toString();
  const n = str.length;

  const memo = new Array(n);
  memo[n - 1] = 1; // 指针临界时的子树的计算结果
  memo[n] = 1; // 指针越界时的子树的计算结果

  const dfs = (str, pointer, memo) => {
    if (memo[pointer]) return memo[pointer]; // 之前存过，直接拿来用

    const temp = Number(str[pointer] + str[pointer + 1]);

    if (temp >= 10 && temp <= 25) {
      memo[pointer] = dfs(str, pointer + 1, memo) + dfs(str, pointer + 2, memo);
    } else {
      memo[pointer] = dfs(str, pointer + 1, memo);
    }

    return memo[pointer]; // 当前子树的计算结果向上返回
  };

  return dfs(str, 0, memo);
};
